package com.qezhhnjy.leetcode.question.tree;

import com.qezhhnjy.leetcode.entity.Node;
import javafx.util.Pair;

import java.util.LinkedList;
import java.util.List;

/**
 * @author qezhhnjy
 * @date 2020/12/19-0:56
 * <p>
 * 给定一个 N 叉树，找到其最大深度。
 * <p>
 * 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
 */
public class NTreeMaxDepth {

    public int maxDepth(Node root) {
        if (root == null) return 0;

        List<Node> children = root.children;
        int max = 0;
        if (children != null) {
            for (Node child : children) {
                int temp = maxDepth(child);
                if (temp > max) max = temp;
            }
        }
        return max + 1;
    }

    // 迭代方法
    public int iteration(Node root) {
        LinkedList<Pair<Node, Integer>> stack = new LinkedList<>();

        if (root != null) {
            stack.add(new Pair<>(root, 1));
        }

        int depth = 0;
        while (!stack.isEmpty()) {
            Pair<Node, Integer> current = stack.poll();
            root = current.getKey();
            int current_depth = current.getValue();
            if (root != null) {
                depth = Math.max(depth, current_depth);
                for (Node child : root.children) {
                    stack.add(new Pair<>(child, current_depth + 1));
                }
            }
        }
        return depth;
    }
}
